{
 "metadata": {
  "name": "",
  "signature": "sha256:4f5b48ad10e743cc729eb58ee7d8d9f68063899f83e8219178a79c1407fdab22"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "\u5feb\u901f\u6392\u5e8f \u6f14\u793a"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "http://pythontutor.com/composingprograms.html#code=def+partion(array,+p,+r)%3A%0A++++x+%3D+array%5Br%5D%0A++++i+%3D+p+-+1%0A++++for+j+in+range(p,+r)%3A%0A++++++++if+(array%5Bj%5D+%3C+x)%3A%0A++++++++++++i%2B%3D1%0A++++++++++++array%5Bj%5D,+array%5Bi%5D+%3D+array%5Bi%5D,+array%5Bj%5D%0A%0A++++i%2B%3D1%0A++++array%5Bi%5D,+array%5Br%5D+%3D+array%5Br%5D,+array%5Bi%5D%0A++++return+i%0A%0Adef+quick_sort(array,+p,+r)%3A%0A++++if+p+%3C+r%3A%0A++++++++q+%3D+partion(array,+p,+r)%0A++++++++quick_sort(array,+p,+q+-+1)%0A++++++++quick_sort(array,+q+%2B+1,+r)%0A%0Aif+__name__+%3D%3D+%22__main__%22%3A%0A++++array+%3D+%5B23,+3,+5,+1%5D%0A++++quick_sort(array,+0,+len(array)+-+1)%0A++++print(array)&mode=display&origin=composingprograms.js&cumulative=true&py=3&rawInputLstJSON=%5B%5D&curInstr=58"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def partion(array, p, r):\n",
      "    x = array[r]\n",
      "    i = p - 1\n",
      "    for j in range(p, r):\n",
      "        if (array[j] < x):\n",
      "            i+=1\n",
      "            array[j], array[i] = array[i], array[j]\n",
      "\n",
      "    i+=1\n",
      "    array[i], array[r] = array[r], array[i]\n",
      "    return i\n",
      "\n",
      "def quick_sort(array, p, r):\n",
      "    if p < r:\n",
      "        q = partion(array, p, r)\n",
      "        quick_sort(array, p, q - 1)\n",
      "        quick_sort(array, q + 1, r)\n",
      "\n",
      "if __name__ == \"__main__\":\n",
      "    array = [23, 3, 5, 1]\n",
      "    quick_sort(array, 0, len(array) - 1)\n",
      "    print(array)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[1, 3, 5, 23]\n"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "\u4e8c\u5206\u67e5\u627e"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "http://pythontutor.com/composingprograms.html#code=def+search(seq,+key)%3A%0A++++lo+%3D+0%0A++++hi+%3D+len(seq)+-+1%0A++++lo_value+%3D+seq%5Blo%5D%0A++++hi_value+%3D+seq%5Bhi%5D%0A%0A++++while+hi+%3E%3D+lo%3A%0A++++++++mid+%3D+lo+%2B+(hi+-+lo)+//+2%0A++++++++mid_value+%3D+seq%5Bmid%5D%0A++++++++if+seq%5Bmid%5D+%3C+key%3A%0A++++++++++++lo+%3D+mid+%2B+1%0A++++++++++++lo_value+%3D+seq%5Blo%5D%0A++++++++elif+seq%5Bmid%5D+%3E+key%3A%0A++++++++++++hi+%3D+mid+-+1%0A++++++++++++hi_value+%3D+seq%5Bhi%5D%0A++++++++else%3A%0A++++++++++++return+mid%0A++++return+False%0A++++%0A++++%0Asearch(%5B1,2,5,6,22,33,55,100%5D,56)&mode=display&origin=composingprograms.js&cumulative=true&py=3&rawInputLstJSON=%5B%5D&curInstr=16"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def search(seq, key):\n",
      "    lo = 0\n",
      "    hi = len(seq) - 1\n",
      "    lo_value = seq[lo]\n",
      "    hi_value = seq[hi]\n",
      "\n",
      "    while hi >= lo:\n",
      "        mid = lo + (hi - lo) // 2\n",
      "        mid_value = seq[mid]\n",
      "        if seq[mid] < key:\n",
      "            lo = mid + 1\n",
      "            lo_value = seq[lo]\n",
      "        elif seq[mid] > key:\n",
      "            hi = mid - 1\n",
      "            hi_value = seq[hi]\n",
      "        else:\n",
      "            return mid\n",
      "    return False\n",
      "    \n",
      "    \n",
      "search([1,2,5,6,22,33,55,100],56)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "False"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "GCD"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "http://pythontutor.com/visualize.html#code=x+%3D+%5B1,+2,+3%5D%0Ay+%3D+%5B4,+5,+6%5D%0Az+%3D+y%0Ay+%3D+x%0Ax+%3D+z%0A%0Ax+%3D+%5B1,+2,+3%5D+%23+a+different+%5B1,+2,+3%5D+list!%0Ay+%3D+x%0Ax.append(4)%0Ay.append(5)%0Az+%3D+%5B1,+2,+3,+4,+5%5D+%23+a+different+list!%0Ax.append(6)%0Ay.append(7)%0Ay+%3D+%22hello%22%0A%0A%0Adef+foo(lst)%3A%0A++++lst.append(%22hello%22)%0A++++bar(lst)%0A%0Adef+bar(myLst)%3A%0A++++print(myLst)%0A%0Afoo(x)%0Afoo(z)&mode=edit&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&drawParentPointers=false&textReferences=false&showOnlyOutputs=false&py=2&rawInputLstJSON=%5B%5D"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def gcd(a,b):\n",
      "    if b==0:return a\n",
      "    return gcd(b,a%b)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "gcd(20,30)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "10"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}